{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概念及简单问题\n",
    "根据百度百科的说法：“程序调用自身的编程技巧称为递归（ recursion）”，这种说法也没错，但是递归绝不是简单的调用自身。所以我更喜欢这种说法：“递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到可以被很简单直接解决。通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数。”  \n",
    "![递归示意图]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "就像阿西莫夫（ l.Asimov） 的“机器人三定律”一样，递归算法也要遵循三条重要的定律：\n",
    "- 递归算法必须有个基本结束条件\n",
    "- 递归算法必须改变自己的状态并向基本结束条件演进\n",
    "- 递归算法必须递归地调用自身"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 数列求和\n",
    "假如我们有一组列表list=[3,1,5,4,6,8,9,1,4]，不使用for/while循环，如何使用递归的方式来对其进行求和呢？如何一步一步构建出递归函数呢？\n",
    "\n",
    "**Step1：将问题分解为子问题**\n",
    "\n",
    "求列表元素的和，进一步分解其实就是求取一个元素与其他元素相加的和，因此我们可以这样考虑为：  \n",
    "3+(...)  \n",
    "3+(1+(...))  \n",
    "3+(1+(+5+(...)))  \n",
    "...  \n",
    "3+(1+(+5+(...+4)))\n",
    "\n",
    "这样我们就将列表求和问题分解为一步一步相加的问题。\n",
    "\n",
    "**Step2：确定结束条件**\n",
    "\n",
    "根据Step1的推导，在最后一层应该只剩下一个元素，即当len(list)的长度为1时，可以直接返回这个元素，不需要再继续运算了，所以我们的结束条件就是：当list长度为1时，返回元素本身。\n",
    "\n",
    "**Step3：不断调用自己，改变自己的状态并向基本结束条件演进**\n",
    "\n",
    "Step2中，我们定义了基本结束条件，接下来就是让算法不断地向基本结束条件演进，演进的方式就是要不断缩小list的长度，直至len(list)==1。因此我们在每递进一次时，都将第一个元素取出，然后与剩余元素相加，以此来达到缩短list长度。  \n",
    "最终代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-01T03:23:21.834578Z",
     "iopub.status.busy": "2020-08-01T03:23:21.834578Z",
     "iopub.status.idle": "2020-08-01T03:23:21.842557Z",
     "shell.execute_reply": "2020-08-01T03:23:21.841558Z",
     "shell.execute_reply.started": "2020-08-01T03:23:21.834578Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 1, 5, 4, 6, 8, 9, 1, 4]\n",
      "[1, 5, 4, 6, 8, 9, 1, 4]\n",
      "[5, 4, 6, 8, 9, 1, 4]\n",
      "[4, 6, 8, 9, 1, 4]\n",
      "[6, 8, 9, 1, 4]\n",
      "[8, 9, 1, 4]\n",
      "[9, 1, 4]\n",
      "[1, 4]\n",
      "[4]\n",
      "41\n"
     ]
    }
   ],
   "source": [
    "# 使用递归方式求取列表的和\n",
    "def list_sum(num_list):\n",
    "    print(num_list)\n",
    "    if len(num_list) == 1:\n",
    "        return num_list[0]\n",
    "    else:\n",
    "        return num_list[0] + list_sum(num_list[1:])\n",
    "print(list_sum([3,1,5,4,6,8,9,1,4]))\n",
    "a=6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递：通过不断调用自身，不断缩小list尺寸，直至list只剩一个元素；\n",
    "\n",
    "归：当只剩最后一个元素后，开始逐层return，返回当前层与底层的和，不断叠加，直至第一层，运算结束；\n",
    "\n",
    "可以这样说，在本例中，递是在构建公式，归则是计算结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 打印文件夹及子文件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T10:45:08.577773Z",
     "iopub.status.busy": "2020-08-02T10:45:08.576820Z",
     "iopub.status.idle": "2020-08-02T10:45:08.608825Z",
     "shell.execute_reply": "2020-08-02T10:45:08.606826Z",
     "shell.execute_reply.started": "2020-08-02T10:45:08.577773Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "machine_learning-checkpoint.ipynb\n",
      "Python-OpenCV分割图像查绿豆的个数Python-OpenCV分割图像查绿豆的个数-checkpoint.ipynb\n",
      "机器学习-checkpoint.ipynb\n",
      "tset-checkpoint.png\n",
      "beans.jpg\n",
      "tset.png\n",
      "wolfberry.jpg\n",
      "wolfberry.png\n",
      "machine_learning.ipynb\n",
      "Python-OpenCV分割图像查绿豆的个数Python-OpenCV分割图像查绿豆的个数.ipynb\n",
      "机器学习.ipynb\n"
     ]
    }
   ],
   "source": [
    "# 定义的file_display函数以某个目录(/home/pushy)作为遍历的起点.遇到一个子目录时，就先接着遍历子目录(递归调用函数)。遇到一个文件时，就直接对改文件进行操作(这里只打印出文件的文件名):\n",
    "import os\n",
    "def file_display(filepath):\n",
    "    for each in os.listdir(filepath):\n",
    "        # 得到文件的绝对路径:\n",
    "        absolute_path = os.path.join(filepath, each)\n",
    "        # 得到是否为文件还是目录的布尔值:\n",
    "        is_file = os.path.isfile(absolute_path)\n",
    "        if is_file:\n",
    "            # 当前的绝对路径为文件:\n",
    "            print(each)\n",
    "        else:\n",
    "            # 当前的绝对路径为目录:\n",
    "            file_display(absolute_path)\n",
    "\n",
    "file_display('D:/File/00 Work File/JupyterProjects/30 机器学习')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。\n",
    "\n",
    "例如上边的两个例子，第一个例子是递归，第二个人例子是尾递归。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-28T02:14:26.228428Z",
     "iopub.status.busy": "2020-07-28T02:14:26.227431Z",
     "iopub.status.idle": "2020-07-28T02:14:26.233231Z",
     "shell.execute_reply": "2020-07-28T02:14:26.231847Z",
     "shell.execute_reply.started": "2020-07-28T02:14:26.228428Z"
    }
   },
   "source": [
    "### 阶乘\n",
    "1. 写一个关于计算某个数阶乘的递归算法fact(n) return n*n-1*n-2…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-28T02:55:12.627332Z",
     "iopub.status.busy": "2020-07-28T02:55:12.626301Z",
     "iopub.status.idle": "2020-07-28T02:55:12.634657Z",
     "shell.execute_reply": "2020-07-28T02:55:12.633140Z",
     "shell.execute_reply.started": "2020-07-28T02:55:12.627332Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fact(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*fact(n-1)\n",
    "fact(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 字符转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 将一个整数转化为二进制到十六进制之间任意进制的字符串形式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-28T03:53:06.042964Z",
     "iopub.status.busy": "2020-07-28T03:53:06.042964Z",
     "iopub.status.idle": "2020-07-28T03:53:06.055246Z",
     "shell.execute_reply": "2020-07-28T03:53:06.054249Z",
     "shell.execute_reply.started": "2020-07-28T03:53:06.042964Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "to_str1(num,n) : 1010\n"
     ]
    }
   ],
   "source": [
    "def to_str1(n, base):\n",
    "    convert_string = \"0123456789ABCDEF\"\n",
    "    if n < base:\n",
    "        return convert_string[n]\n",
    "    else:\n",
    "        return to_str1(n // base, base) + convert_string[n % base]\n",
    "print('to_str1(num,n) :', to_str1(10 ,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈帧：实现递归(待详细了解)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 331,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-29T07:40:20.654916Z",
     "iopub.status.busy": "2020-07-29T07:40:20.654916Z",
     "iopub.status.idle": "2020-07-29T07:40:20.724929Z",
     "shell.execute_reply": "2020-07-29T07:40:20.723963Z",
     "shell.execute_reply.started": "2020-07-29T07:40:20.654916Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5AD\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "rStack = Stack()\n",
    "\n",
    "def to_str(n,base):\n",
    "    conver_string = \"0123456789ABCDEF\"\n",
    "    while n>0:\n",
    "        if n<base:\n",
    "            rStack.push(conver_string[n])\n",
    "        else:\n",
    "            rStack.push(conver_string[n%base])\n",
    "        n //= base\n",
    "    res = \"\"\n",
    "    while not rStack.isEmpty():\n",
    "        res += str(rStack.pop())\n",
    "    return res\n",
    "\n",
    "print(to_str(1453,16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后边可以将帧栈应用在走迷宫上，用于返回路径。  \n",
    "实用场景：自动驾驶路径选择。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "execution": {
     "iopub.status.idle": "2020-07-28T04:29:02.926428Z",
     "shell.execute_reply": "2020-07-28T04:29:02.922115Z",
     "shell.execute_reply.started": "2020-07-28T04:29:02.849271Z"
    }
   },
   "source": [
    "## 可视化递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 绘制递归螺线"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-01T11:09:00.357101Z",
     "iopub.status.busy": "2020-08-01T11:09:00.356103Z",
     "iopub.status.idle": "2020-08-01T11:13:43.830614Z",
     "shell.execute_reply": "2020-08-01T11:13:43.829617Z",
     "shell.execute_reply.started": "2020-08-01T11:09:00.357101Z"
    }
   },
   "outputs": [],
   "source": [
    "# turtle 是 Python 所有版本的标准库，插图的工具\n",
    "import turtle\n",
    "import time\n",
    "time.sleep(2)\n",
    "myTurtle = turtle.Turtle()\n",
    "myWin = turtle.Screen()\n",
    "# turtle.setup(width=100,height=100)\n",
    "def drawSpiral(myTurtle, lineLen):\n",
    "    if lineLen > 0:\n",
    "        myTurtle.forward(lineLen)\n",
    "    else:\n",
    "         return   \n",
    "    time.sleep(0.1)\n",
    "    myTurtle.left(90)\n",
    "    lineLen = lineLen-5\n",
    "    drawSpiral(myTurtle, lineLen)\n",
    "drawSpiral(myTurtle,100)\n",
    "myWin.exitonclick()\n",
    "# 调用函数 myWin.exitonclick()，这是一个方便的缩小窗口的方法，\n",
    "# 使乌龟进入等待模式，直到你单击窗口，然后程序清理并退出。\n",
    "# myWin.exitonclick()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 绘制递归树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-01T13:06:19.625673Z",
     "iopub.status.busy": "2020-08-01T13:06:19.624676Z",
     "iopub.status.idle": "2020-08-01T13:07:09.605849Z",
     "shell.execute_reply": "2020-08-01T13:07:09.602853Z",
     "shell.execute_reply.started": "2020-08-01T13:06:19.625673Z"
    }
   },
   "outputs": [],
   "source": [
    "# 基本树\n",
    "import turtle\n",
    "c = 90\n",
    "def tree(branchLen,t):\n",
    "    if branchLen > 15:\n",
    "        t.forward(branchLen)\n",
    "        t.right(c)\n",
    "        tree(branchLen-15,t)\n",
    "        t.left(c*2)\n",
    "        tree(branchLen-15,t)\n",
    "        t.right(c)\n",
    "        t.backward(branchLen)\n",
    "        \n",
    "def main():\n",
    "    t = turtle.Turtle()\n",
    "    myWin = turtle.Screen()\n",
    "    turtle.setup(width=0.9,height=0.9)\n",
    "    t.left(90)\n",
    "    t.up()\n",
    "    t.backward(100)\n",
    "    t.down()\n",
    "    t.color(\"green\")\n",
    "    tree(80,t)\n",
    "    myWin.exitonclick()\n",
    "main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T07:35:20.199647Z",
     "iopub.status.busy": "2020-08-06T07:35:20.197747Z",
     "iopub.status.idle": "2020-08-06T07:35:50.306535Z",
     "shell.execute_reply": "2020-08-06T07:35:50.304396Z",
     "shell.execute_reply.started": "2020-08-06T07:35:20.199647Z"
    }
   },
   "outputs": [
    {
     "ename": "Terminator",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTerminator\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-2-9f45026150f7>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     71\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     72\u001b[0m \u001b[0mmain\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 73\u001b[1;33m \u001b[0mdone\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\Anaconda3\\lib\\turtle.py\u001b[0m in \u001b[0;36mmainloop\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;31mTerminator\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# 好看的树，参考https://blog.csdn.net/u012424148/article/details/88890478\n",
    "import turtle\n",
    "import random\n",
    "from turtle import *\n",
    "from time import sleep\n",
    " \n",
    "t = turtle.Turtle()\n",
    "w = turtle.Screen()\n",
    " \n",
    "def tree(branchLen, t):\n",
    "    if branchLen > 3:\n",
    "        if 8 <= branchLen <= 12:\n",
    "            if random.randint(0, 2) == 0:\n",
    "                t.color('snow')\n",
    "            else:\n",
    "                t.color('lightcoral')\n",
    "            t.pensize(branchLen / 3)\n",
    "        elif branchLen < 8:\n",
    "            if random.randint(0, 1) == 0:\n",
    "                t.color('snow')\n",
    "            else:\n",
    "                t.color('lightcoral')\n",
    "            t.pensize(branchLen / 2)\n",
    "        else:\n",
    "            t.color('sienna')\n",
    "            t.pensize(branchLen / 10)\n",
    " \n",
    "        t.forward(branchLen)\n",
    "        a = 1.5 * random.random()\n",
    "        t.right(20*a)\n",
    "        b = 1.5 * random.random()\n",
    "        tree(branchLen-10*b, t)\n",
    "        t.left(40*a)\n",
    "        tree(branchLen-10*b, t)\n",
    "        t.right(20*a)\n",
    "        t.up()\n",
    "        t.backward(branchLen)\n",
    "        t.down()\n",
    " \n",
    " \n",
    "def petal(m, t):  # 树下花瓣\n",
    "    for i in range(m):\n",
    "        a = 200 - 400 * random.random()\n",
    "        b = 10 - 20 * random.random()\n",
    "        t.up()\n",
    "        t.forward(b)\n",
    "        t.left(90)\n",
    "        t.forward(a)\n",
    "        t.down()\n",
    "        t.color(\"lightcoral\")\n",
    "        t.circle(1)\n",
    "        t.up()\n",
    "        t.backward(a)\n",
    "        t.right(90)\n",
    "        t.backward(b)\n",
    " \n",
    " \n",
    "def main():\n",
    "    t = turtle.Turtle()\n",
    "    myWin = turtle.Screen()\n",
    "    getscreen().tracer(5, 0)\n",
    "    turtle.screensize(bg='wheat')\n",
    "    t.left(90)\n",
    "    t.up()\n",
    "    t.backward(150)\n",
    "    t.down()\n",
    "    t.color('sienna')\n",
    "    tree(60, t)\n",
    "    petal(100, t)\n",
    " \n",
    "    myWin.exitonclick()\n",
    " \n",
    "main()\n",
    "done()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T07:36:50.995619Z",
     "iopub.status.busy": "2020-08-06T07:36:50.994619Z",
     "iopub.status.idle": "2020-08-06T07:37:00.565722Z",
     "shell.execute_reply": "2020-08-06T07:37:00.563738Z",
     "shell.execute_reply.started": "2020-08-06T07:36:50.995619Z"
    }
   },
   "outputs": [],
   "source": [
    "# 好看的树，参考：https://blog.csdn.net/u012424148/article/details/88890478\n",
    "from turtle import *\n",
    "from random import *\n",
    "from math import *\n",
    " \n",
    "def tree(n, l):\n",
    "    pd() # 下笔\n",
    "    # 阴影效果\n",
    "    t = cos(radians(heading() + 45)) / 8 + 0.25\n",
    "    pencolor(t, t, t)\n",
    "    pensize(n / 3)\n",
    "    forward(l) # 画树枝\n",
    " \n",
    " \n",
    "    if n > 0:\n",
    "        b = random() * 15 + 10 # 右分支偏转角度\n",
    "        c = random() * 15 + 10 # 左分支偏转角度\n",
    "        d = l * (random() * 0.25 + 0.7) # 下一个分支的长度\n",
    "        # 右转一定角度，画右分支\n",
    "        right(b)\n",
    "        tree(n - 1, d)\n",
    "        # 左转一定角度，画左分支\n",
    "        left(b + c)\n",
    "        tree(n - 1, d)\n",
    " \n",
    "        # 转回来\n",
    "        right(c)\n",
    "    else:\n",
    "        # 画叶子\n",
    "        right(90)\n",
    "        n = cos(radians(heading() - 45)) / 4 + 0.5\n",
    "        pencolor(n, n*0.8, n*0.8)\n",
    "        circle(3)\n",
    "        left(90)\n",
    " \n",
    "        # 添加0.3倍的飘落叶子\n",
    "        if(random() > 0.7):\n",
    "            pu()\n",
    "            # 飘落\n",
    "            t = heading()\n",
    "            an = -40 + random()*40\n",
    "            setheading(an)\n",
    "            dis = int(800*random()*0.5 + 400*random()*0.3 + 200*random()*0.2)\n",
    "            forward(dis)\n",
    "            setheading(t)\n",
    " \n",
    " \n",
    "            # 画叶子\n",
    "            pd()\n",
    "            right(90)\n",
    "            n = cos(radians(heading() - 45)) / 4 + 0.5\n",
    "            pencolor(n*0.5+0.5, 0.4+n*0.4, 0.4+n*0.4)\n",
    "            circle(2)\n",
    "            left(90)\n",
    "            pu()\n",
    " \n",
    "            #返回\n",
    "            t = heading()\n",
    "            setheading(an)\n",
    "            backward(dis)\n",
    "            setheading(t)\n",
    " \n",
    "    pu()\n",
    "    backward(l)# 退回\n",
    " \n",
    "bgcolor(0.5, 0.5, 0.5) # 背景色\n",
    "ht() # 隐藏turtle\n",
    "speed(0) # 速度，1-10渐进，0最快\n",
    "tracer(0, 0)\n",
    "pu() # 抬笔\n",
    "backward(100)\n",
    "left(90) # 左转90度\n",
    "pu() # 抬笔\n",
    "backward(300) # 后退300\n",
    "tree(12, 100) # 递归7层\n",
    "done()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 谢尔宾斯基三角形"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle\n",
    "\n",
    "def drawTriangle(points,color,myTurtle):\n",
    "    myTurtle.fillcolor(color)\n",
    "    myTurtle.up()\n",
    "    myTurtle.goto(points[0][0],points[0][1])\n",
    "    myTurtle.down()\n",
    "    myTurtle.begin_fill()\n",
    "    myTurtle.goto(points[1][0],points[1][1])\n",
    "    myTurtle.goto(points[2][0],points[2][1])\n",
    "    myTurtle.goto(points[0][0],points[0][1])\n",
    "    myTurtle.end_fill()\n",
    "\n",
    "def getMid(p1,p2):\n",
    "    return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)\n",
    "\n",
    "def sierpinski(points,degree,myTurtle):\n",
    "    colormap = ['blue','red','green','white','yellow',\n",
    "                'violet','orange']\n",
    "    drawTriangle(points,colormap[degree],myTurtle)\n",
    "    if degree > 0:\n",
    "        sierpinski([points[0],\n",
    "                        getMid(points[0], points[1]),\n",
    "                        getMid(points[0], points[2])],\n",
    "                   degree-1, myTurtle)\n",
    "        sierpinski([points[1],\n",
    "                        getMid(points[0], points[1]),\n",
    "                        getMid(points[1], points[2])],\n",
    "                   degree-1, myTurtle)\n",
    "        sierpinski([points[2],\n",
    "                        getMid(points[2], points[1]),\n",
    "                        getMid(points[0], points[2])],\n",
    "                   degree-1, myTurtle)\n",
    "\n",
    "def main():\n",
    "   myTurtle = turtle.Turtle()\n",
    "   myWin = turtle.Screen()\n",
    "   myPoints = [[-100,-50],[0,100],[100,-50]]\n",
    "   sierpinski(myPoints,3,myTurtle)\n",
    "   myWin.exitonclick()\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 复杂问题的递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 河内塔问题\n",
    "他受到一个关于印度教寺庙的传说\n",
    "的启发，故事中这一问题交由年轻僧侣们解决。最开始，僧侣们得到三根杆子， 64个金圆盘堆叠在\n",
    "其中一根上, 每个圆盘比其下的小一点。僧侣们的任务是将64个圆盘从一根杆上转移到另一根杆上，\n",
    "但有两项重要的限制,一是他们一次只能移动一个圆盘,一是不能将大圆盘放在小圆盘之上。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-31T10:31:18.174428Z",
     "iopub.status.busy": "2020-07-31T10:31:18.173433Z",
     "iopub.status.idle": "2020-07-31T10:31:18.184913Z",
     "shell.execute_reply": "2020-07-31T10:31:18.182921Z",
     "shell.execute_reply.started": "2020-07-31T10:31:18.174428Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moving disk from A to B\n",
      "moving disk from A to C\n",
      "moving disk from B to C\n",
      "moving disk from A to B\n",
      "moving disk from C to A\n",
      "moving disk from C to B\n",
      "moving disk from A to B\n"
     ]
    }
   ],
   "source": [
    "# 一开始盘子都在起始杆上\n",
    "# Python 提供了我们需要调用的隐含的栈。\n",
    "def moveTower(height,fromPole, toPole, withPole):\n",
    "    if height >= 1:\n",
    "        moveTower(height-1,fromPole,withPole,toPole)\n",
    "        moveDisk(fromPole,toPole)\n",
    "        moveTower(height-1,withPole,toPole,fromPole)\n",
    "def moveDisk(fp,tp):\n",
    "    print(\"moving disk from\",fp,\"to\",tp)\n",
    "moveTower(3,'A', 'B', 'C')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 探索迷宫"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T11:58:12.160604Z",
     "iopub.status.busy": "2020-08-02T11:58:12.160604Z",
     "iopub.status.idle": "2020-08-02T11:58:12.228928Z",
     "shell.execute_reply": "2020-08-02T11:58:12.227931Z",
     "shell.execute_reply.started": "2020-08-02T11:58:12.160604Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 创建迷宫\n",
    "import numpy as np\n",
    "def gen_maze(m, n):\n",
    "    \"\"\"\n",
    "    生成随机迷宫阵列\n",
    "    :param m: int 类型\n",
    "    :param n: int 类型\n",
    "    :return: maze\n",
    "    \"\"\"\n",
    "    m += 2\n",
    "    n += 2 # m 和 n 均 +2 是为了构造最外层的 1\n",
    "    maze = [[9 for i in range(n)] for j in range(m)] # 初始化大小为 m * n，值全为 1 的二维矩阵\n",
    "    maze[0][1] = 1\n",
    "    maze[m-1][n-2] = 0\n",
    "    for x in range(1, m-1):\n",
    "        for y in range(1, n-1):\n",
    "            \"\"\"\n",
    "            这里 x, y 取值范围为 x ∈ [1, m-1)，y ∈ [1, n-1) 是因为我们令此迷宫的最外层（四周）均为 1，如：\n",
    "            考察 3 * 3 矩阵，一种可能的阵列为：\n",
    "            [\n",
    "            _ |←--- n:y ---→|\n",
    "            ↑ [1, 1, 1, 1, 1],\n",
    "            | [1, 0, 1, 0, 1],\n",
    "          m:x [1, 0, 0, 1, 1],\n",
    "            | [1, 1, 0, 0, 1],\n",
    "            ↓ [1, 1, 1, 1, 1] \n",
    "            ]\n",
    "            \"\"\"\n",
    "            if (x == 1 and y == 1) or (x == m - 2 and y == n - 2):\n",
    "                maze[x][y] = 0 # 起始点和终点必为 0\n",
    "            else:\n",
    "                if np.random.randint(0, 2):\n",
    "                    maze[x][y] = 9 # 在最外层均为 1 的情况下内部随机取 0，9\n",
    "                else:\n",
    "                     maze[x][y] = 0 \n",
    "    return maze\n",
    "    \n",
    "\n",
    "\n",
    "# 打印迷宫\n",
    "def print_maze(maze, end1='  ', end2='\\n\\n', xs=0, xe=0, ys=0, ye=0):\n",
    "  \"\"\"\n",
    "  输出迷宫矩阵，非必要，可注释删除\n",
    "  :param maze: 一个 m*n 大小的二维矩阵迷宫\n",
    "  :param text: 输出提示\n",
    "  :param end1: 控制每行尾结束符\n",
    "  :param end2: 控制每行尾结束符\n",
    "  :param xs: 控制是否输出最上方的 1 环，0 为输出，1 为不输出\n",
    "  :param xe: 控制是否输出最上方的 1 环，0 为输出，1 为不输出\n",
    "  :param ys: 控制是否输出最上方的 1 环，0 为输出，1 为不输出\n",
    "  :param ye: 控制是否输出最上方的 1 环，0 为输出，1 为不输出\n",
    "  \"\"\"\n",
    "  n, m = len(maze[0]), len(maze)\n",
    "  for x in range(xs, m-xe):\n",
    "    for y in range(ys, n-ye):\n",
    "        if(maze[x][y] == 0):\n",
    "            print('\\033[0;42m',maze[x][y] ,'\\033[0m', end=end1)\n",
    "        elif(maze[x][y] == 9):\n",
    "             print('\\033[0;40m',maze[x][y]  ,'\\033[0m', end=end1)\n",
    "        else:\n",
    "            print('\\033[0;41m',maze[x][y] ,'\\033[0m', end=end1)\n",
    "    print(end=end2)\n",
    "new_maze = gen_maze(3,4)\n",
    "# print(new_maze)\n",
    "print_maze(new_maze)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-29T10:13:59.613794Z",
     "iopub.status.busy": "2020-07-29T10:13:59.612797Z",
     "iopub.status.idle": "2020-07-29T10:13:59.703080Z",
     "shell.execute_reply": "2020-07-29T10:13:59.701079Z",
     "shell.execute_reply.started": "2020-07-29T10:13:59.613794Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "下一步到终点了\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;41m 1 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "import os\n",
    "# 确定方向\n",
    "w1_maze =new_maze\n",
    "# print(w1_maze)\n",
    "pos1_mouse = [0,1]\n",
    "end_pos =[len(w1_maze)-1,len(w1_maze[0])-2]\n",
    "def mark(pos,w_maze):\n",
    "    w_maze[pos[0]][pos[1]] += 1 # 将走过的位置标记为 2\n",
    "\n",
    "def tar_dir(now_pos,w_maze):\n",
    "#     print('now_pos:',now_pos,w_maze[now_pos[0]][now_pos[1]])\n",
    "    dir =[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "    d = w_maze[now_pos[0]+1][now_pos[1]]\n",
    "    u = w_maze[now_pos[0]-1][now_pos[1]]\n",
    "    r = w_maze[now_pos[0]][now_pos[1]+1]\n",
    "    l = w_maze[now_pos[0]][now_pos[1]-1]\n",
    "    dir_list = [d,r,u,l]\n",
    "#     print('dir_list:',dir_list)\n",
    "    min_index = dir_list.index(min(dir_list))\n",
    "#     return True, dir[min_index]\n",
    "    if min_index < 5 :\n",
    "        return True, dir[min_index]\n",
    "    else:\n",
    "        return False,[]\n",
    "\n",
    "# 递归走迷宫\n",
    "def walk(pos_mouse,w_maze,finsh_flag=False):\n",
    "    # 确定是否有方向可走\n",
    "    result = tar_dir(pos_mouse,w_maze)\n",
    "#     time.sleep(1)\n",
    "#     os.system('cls')\n",
    "    if result[0]:\n",
    "        dir = result[1]\n",
    "#         print('有方向:', dir)\n",
    "        # 向可走的方向走一步，打个点\n",
    "        pos_mouse[0]+=dir[0]\n",
    "        pos_mouse[1]+=dir[1]\n",
    "#         print_maze(w_maze)\n",
    "        mark(pos_mouse,w_maze)\n",
    "#         print(pos_mouse,end_pos,pos_mouse == end_pos)\n",
    "        if pos_mouse == end_pos:\n",
    "            print('下一步到终点了')\n",
    "            print_maze(w_maze)\n",
    "#             return w_maze\n",
    "        else:\n",
    "            # 继续走\n",
    "#             print('下一步没到终点')\n",
    "            walk(pos_mouse,w_maze)\n",
    "    else:\n",
    "#         print('没有方向')\n",
    "        mark(pos_mouse,w_maze)\n",
    "#         return \n",
    "walk(pos1_mouse,w1_maze)\n",
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上边的代码虽然能够计算出结果，但是并不能体现递归的精髓，因为一直在循环调用原方法，即使走回头路，理论上走回头路应该return回去，释放资源，上述代码没有，所有资源都是在找到终点后一起释放的，所以在走复杂迷宫时很容易内存溢出。  \n",
    "对代码做一下修改，添加返回值，在不能走的情况下即return释放内存,如下所示，下图中的代码可以处理更复杂的迷宫。  \n",
    "理论上来讲仍会存在内存溢出的情况，但已明显改善，这种可以在前期加限值来处理，例如本例中，限值迷宫生成的大小，只要不超过一定值，就不会内存溢出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T12:02:13.726743Z",
     "iopub.status.busy": "2020-08-02T12:02:13.726743Z",
     "iopub.status.idle": "2020-08-02T12:02:13.746652Z",
     "shell.execute_reply": "2020-08-02T12:02:13.745654Z",
     "shell.execute_reply.started": "2020-08-02T12:02:13.726743Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "迷宫无解\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 3 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;41m 2 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n",
      "\u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \u001b[0;42m 0 \u001b[0m  \u001b[0;40m 9 \u001b[0m  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "import os\n",
    "import numpy as np\n",
    "# 确定方向\n",
    "# print(end_pos)\n",
    "def mark(pos,w_maze_m):\n",
    "    w_maze_m[pos[0]][pos[1]] += 1 # 将走过的位置标记为 2\n",
    "    return w_maze_m\n",
    "\n",
    "def tar_dir(now_pos,w_maze):\n",
    "#     print('now_pos:',now_pos,w_maze[now_pos[0]][now_pos[1]])\n",
    "    dir =[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "    d = w_maze[now_pos[0]+1][now_pos[1]]\n",
    "    u = w_maze[now_pos[0]-1][now_pos[1]]\n",
    "    r = w_maze[now_pos[0]][now_pos[1]+1]\n",
    "    l = w_maze[now_pos[0]][now_pos[1]-1]\n",
    "    dir_list = [d,r,u,l]\n",
    "#     print('dir_list:',dir_list)\n",
    "#     min_index = dir_list.index(min(dir_list))\n",
    "#     return True, dir[min_index]\n",
    "    # 输出可走方向\n",
    "    open_dir = []\n",
    "    for i in range(0,4):\n",
    "        if dir_list[i] == 0:\n",
    "            open_dir.append(dir[i])\n",
    "    return open_dir\n",
    "\n",
    "# 递归走迷宫\n",
    "def walk(pos_mouse,w_maze):\n",
    "    # 是否到达终点？\n",
    "#     print(pos_mouse)\n",
    "    if pos_mouse == end_pos:\n",
    "#         print('目前在终点')\n",
    "#         w_maze = mark(pos_mouse,w_maze)\n",
    "        \n",
    "        return True,True # ,w_maze  # finish_flag、dead_flag\n",
    "    else:\n",
    "        # 确定是否有方向可走\n",
    "        dirs = tar_dir(pos_mouse,w_maze)\n",
    "        if dirs:\n",
    "            # 若有，依此遍历可走方向\n",
    "#             print(pos_mouse,'可以走',dirs)\n",
    "            next_pos = pos_mouse\n",
    "            for dir in dirs:\n",
    "                # 向可走的方向走一步，打个点，继续判断下一步是否可走\n",
    "#                 print(next_pos,'开始走',dir)\n",
    "                next_pos[0] += dir[0]\n",
    "                next_pos[1] += dir[1]\n",
    "                w_maze = mark(next_pos,w_maze)\n",
    "                x,y= walk(next_pos, w_maze)\n",
    "                if(x):\n",
    "                    # 到终点了，结束递归\n",
    "                    return True, True# , n\n",
    "                if(y):\n",
    "                    # 不能走再退回去\n",
    "                    next_pos[0] -= dir[0]\n",
    "                    next_pos[1] -= dir[1]\n",
    "                    mark(next_pos,w_maze)\n",
    "#             print(pos_mouse,'前方没路了')\n",
    "            return x,y#,n\n",
    "        else:\n",
    "            # 没有路，原地打个点，返回\n",
    "#             print(pos_mouse,'没路了')\n",
    "            mark(pos_mouse,w_maze)\n",
    "            return False,True\n",
    "\n",
    "w1_maze = gen_maze(np.random.randint(5,10), np.random.randint(5, 10)) # w1是全局变量，所以可以记录路径\n",
    "pos1_mouse = [0,1]\n",
    "end_pos =[len(w1_maze)-1,len(w1_maze[0])-2]\n",
    "x,y = walk(pos1_mouse,w1_maze)\n",
    "if x:\n",
    "    print('到终点了')\n",
    "else: \n",
    "    if y:\n",
    "        print('迷宫无解')\n",
    "    else:\n",
    "        print('有未知情况')\n",
    "print_maze(w1_maze)\n",
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 基本概念\n",
    "动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 相关知识点：有别于动态规划，贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。**在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。**依次解决各子问题，最后一个子问题就是初始问题的解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关于动态规划的一些基本概念，可以参考[百度百科](https://baike.baidu.com/item/动态规划/529408?fr=aladdin)的定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "能采用动态规划求解的问题的一般要具有3个性质：\n",
    "- (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。\n",
    "- (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。\n",
    "- (3)有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分析过程：  \n",
    "- STEP1：分解为子问题\n",
    "- STEP2：确定状态\n",
    "- STEP3：确定边界值(结束条件)\n",
    "- STEP4：确定状态转移方程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "或者参考[这篇博客](https://blog.csdn.net/weixin_38278878/article/details/80037455?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase)的观点，动态规划五部曲： \n",
    "- 1. 判题题意是否为找出一个问题的最优解 \n",
    "- 2. 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题，自上而下则用到了递归技术。\n",
    "- 3. 从下往上分析问题 ，找出这些问题之间的关联（状态转移方程，自下而上用到了迭代技术\n",
    "- 4. 讨论底层的边界问题 \n",
    "- 5. 解决问题（通常使用数组进行迭代求出最优解）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划与递归的比较：\n",
    "- 1. 动态规划和递归都可以用来遍历，例如青蛙跳问题，但递归通过记录之前进行的计算，明显加快了计算速度；(不知道不用做寻优的这个思想叫不叫动态规划，不符合动态规划的定义呀)\n",
    "- 2. 寻优问题，为获得最优解，递归会遍历所有情况，会造成大量的重复计算，而动态规划通过记住之前的计算结果，从而降低寻优时间，例如找零问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 青蛙跳问题  \n",
    "可参考：https://zhuanlan.zhihu.com/p/31628866"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归算法：  \n",
    "- 边界条件\n",
    "    - f(1) = 1  \n",
    "    - f(2) = 2  \n",
    "- 子问题\n",
    "    - f(n) = f(n-1) + f(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T11:42:37.799920Z",
     "iopub.status.busy": "2020-08-02T11:42:37.799920Z",
     "iopub.status.idle": "2020-08-02T11:42:40.129900Z",
     "shell.execute_reply": "2020-08-02T11:42:40.128902Z",
     "shell.execute_reply.started": "2020-08-02T11:42:37.799920Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14930352"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 递归解法\n",
    "def get_way(n):\n",
    "    if n<1:\n",
    "        return 0\n",
    "    elif n ==1:\n",
    "        return 1\n",
    "    elif n==2:\n",
    "        return 2\n",
    "    return get_way(n-1) + get_way(n-2)\n",
    "\n",
    "get_way(35) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据计算统计可以看出，计算30级台阶用了226ms，35级用了2.32s，50级直接不出结果了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T11:55:42.989991Z",
     "iopub.status.busy": "2020-08-02T11:55:42.988994Z",
     "iopub.status.idle": "2020-08-02T11:55:42.998067Z",
     "shell.execute_reply": "2020-08-02T11:55:42.997080Z",
     "shell.execute_reply.started": "2020-08-02T11:55:42.989991Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20365011074\n",
      "{3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89, 11: 144, 12: 233, 13: 377, 14: 610, 15: 987, 16: 1597, 17: 2584, 18: 4181, 19: 6765, 20: 10946, 21: 17711, 22: 28657, 23: 46368, 24: 75025, 25: 121393, 26: 196418, 27: 317811, 28: 514229, 29: 832040, 30: 1346269, 31: 2178309, 32: 3524578, 33: 5702887, 34: 9227465, 35: 14930352, 36: 24157817, 37: 39088169, 38: 63245986, 39: 102334155, 40: 165580141, 41: 267914296, 42: 433494437, 43: 701408733, 44: 1134903170, 45: 1836311903, 46: 2971215073, 47: 4807526976, 48: 7778742049, 49: 12586269025, 50: 20365011074}\n"
     ]
    }
   ],
   "source": [
    "## 动态规划方法，创建一个哈希表，每次把结果放入哈希表，遇到相同参数就取出来\n",
    "def get_way(n,value_dict):\n",
    "    if n<1:\n",
    "        return 0\n",
    "    elif n ==1:\n",
    "        return 1\n",
    "    elif n==2:\n",
    "        return 2\n",
    "    elif n in value_dict:\n",
    "        return value_dict[n]\n",
    "    else:\n",
    "        sum_way = get_way(n-1,value_dict) + get_way(n-2,value_dict)\n",
    "        value_dict[n] = sum_way\n",
    "        return sum_way\n",
    "\n",
    "dict_value = {}\n",
    "print(get_way(50,dict_value))\n",
    "print(dict_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T11:49:55.364911Z",
     "iopub.status.busy": "2020-08-02T11:49:55.363911Z",
     "iopub.status.idle": "2020-08-02T11:49:55.378896Z",
     "shell.execute_reply": "2020-08-02T11:49:55.377390Z",
     "shell.execute_reply.started": "2020-08-02T11:49:55.364911Z"
    }
   },
   "source": [
    "可以看出，经过动态规划优化后，运算速度提升迅速，计算计算30级台阶用了7ms，35级用了7ms，50用了9ms，都是ms级别的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 找零钱问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T12:08:50.048559Z",
     "iopub.status.busy": "2020-08-02T12:08:50.047556Z",
     "iopub.status.idle": "2020-08-02T12:09:02.387215Z",
     "shell.execute_reply": "2020-08-02T12:09:02.385938Z",
     "shell.execute_reply.started": "2020-08-02T12:08:50.048559Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# 递归算法\n",
    "def recMC(coinValueList,change):\n",
    "    minCoins = change\n",
    "    if change in coinValueList:\n",
    "        return 1\n",
    "    else:\n",
    "        for i in [c for c in coinValueList if c <= change]:\n",
    "            numCoins = 1 + recMC(coinValueList,change-i)\n",
    "            if numCoins < minCoins:\n",
    "                minCoins = numCoins\n",
    "    return minCoins\n",
    "\n",
    "print(recMC([1,5,10,25],60))  # 12.34s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T12:28:55.398399Z",
     "iopub.status.busy": "2020-08-02T12:28:55.398399Z",
     "iopub.status.idle": "2020-08-02T12:28:55.415533Z",
     "shell.execute_reply": "2020-08-02T12:28:55.414485Z",
     "shell.execute_reply.started": "2020-08-02T12:28:55.398399Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Making change for 63 requires\n",
      "3 coins\n",
      "They are:\n",
      "21\n",
      "21\n",
      "21\n",
      "The used list is as follows:\n",
      "[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]\n"
     ]
    }
   ],
   "source": [
    "# 动态规划算法\n",
    "def dpMakeChange(coinValueList,change,minCoins,coinsUsed):\n",
    "    for cents in range(change+1):\n",
    "        coinCount = cents\n",
    "        newCoin = 1\n",
    "        for j in [c for c in coinValueList if c <= cents]:\n",
    "            if minCoins[cents-j] + 1 < coinCount:\n",
    "                coinCount = minCoins[cents-j]+1\n",
    "                newCoin = j\n",
    "        minCoins[cents] = coinCount\n",
    "        coinsUsed[cents] = newCoin\n",
    "    return minCoins[change]\n",
    "\n",
    "def printCoins(coinUsed,change):\n",
    "    coin = change\n",
    "    while coin > 0:\n",
    "        thisCoin = coinUsed[coin]\n",
    "        print(thisCoin)\n",
    "        coin = coin - thisCoin\n",
    "\n",
    "def main():\n",
    "    amnt = 63\n",
    "    clist = [1,5,10,21,25]\n",
    "    coinsUsed = [0]*(amnt+1)\n",
    "    coinCount = [0]*(amnt+1)\n",
    "    print(\"Making change for\",amnt,\"requires\")\n",
    "    print(dpMakeChange(clist,amnt,coinCount,coinsUsed),\"coins\")\n",
    "    print(\"They are:\")\n",
    "    printCoins(coinsUsed,amnt)\n",
    "    print(\"The used list is as follows:\")\n",
    "    print(coinsUsed)\n",
    "main()  # 11ms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三角求和问题（后续再写）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-02T10:29:12.882699Z",
     "iopub.status.busy": "2020-08-02T10:29:12.882699Z",
     "iopub.status.idle": "2020-08-02T10:29:12.891632Z",
     "shell.execute_reply": "2020-08-02T10:29:12.891632Z",
     "shell.execute_reply.started": "2020-08-02T10:29:12.882699Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n    7\\n   3 8\\n  8 1 0\\n 2 7 4 4\\n4 5 2 6 5\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "    7\n",
    "   3 8\n",
    "  8 1 0\n",
    " 2 7 4 4\n",
    "4 5 2 6 5\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从最上面的数字三角形中寻找一条顶部到底部的路径，使得路径上的所经过的数字之和最大。路径上的每一步都只能往左下或者右下走，只需要求出最大和即可，不必给出具体路径。  \n",
    "三角形的行数大于1小于等于100，数字为0~99。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T07:34:29.146264Z",
     "iopub.status.busy": "2020-08-06T07:34:29.145160Z",
     "iopub.status.idle": "2020-08-06T07:34:38.427223Z",
     "shell.execute_reply": "2020-08-06T07:34:38.424371Z",
     "shell.execute_reply.started": "2020-08-06T07:34:29.146264Z"
    }
   },
   "outputs": [
    {
     "ename": "Terminator",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTerminator\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-9f45026150f7>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     71\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     72\u001b[0m \u001b[0mmain\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 73\u001b[1;33m \u001b[0mdone\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\Anaconda3\\lib\\turtle.py\u001b[0m in \u001b[0;36mmainloop\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;31mTerminator\u001b[0m: "
     ]
    }
   ],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
